package zuochengyun;

import java.util.Stack;

import list.ListNode;

/**
 * 每k个结点之间逆序
 * @author Administrator
 */
public class ReverseKNodes {

	public ListNode reverseKNodes(ListNode head, int k){
		if(k < 2){
			return head;
		}
		ListNode newHead = head;
		Stack<ListNode> stack = new Stack<>();
		ListNode cur = head;
		ListNode pre = null;	//前一段的尾结点
		ListNode next = null;	//后一段的头结点
		while(cur != null){
			next = cur.next;
			stack.push(cur);
			while(stack.size() == k){
				pre = reLink(stack, pre, next);
				newHead = newHead == head ? cur : newHead;
			}
			cur = next;
		}
		return newHead;
	}
	
	/**
	 * 对栈中的结点进行连接
	 * @return 此段链表反转之后的尾结点
	 */
	public ListNode reLink(Stack<ListNode> stack, ListNode left, ListNode right){
		ListNode cur = stack.pop();
		//如果left不为null, 将此段的头结点连接至left
		if(left != null){
			left.next = cur;
		}
		ListNode next = null;
		while(!stack.isEmpty()){
			next = stack.pop();
			cur.next = next;
			cur = next;
		}
		cur.next = right;
		return cur;
	}
}
